/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class LongestValidParentheses {

	public int longestValidParentheses(String s) {
		int n = s.length();
		int max = 0, sum = 0, cnt = 0;
		for (int i = 0; i < n; ++i) {
			sum += (s.charAt(i) == '(' ? 1 : -1);
			cnt++;
			if (sum == 0) {
				max = Math.max(max, cnt);
			} else if (sum < 0) {
				sum = 0;
				cnt = 0;
			}
		}
		sum = 0;
		cnt = 0;
		for (int i = n - 1; i >= 0; i--) {
			sum += (s.charAt(i) == ')' ? 1 : -1);
			cnt++;
			if (sum == 0) {
				max = Math.max(max, cnt);
			} else if (sum < 0) {
				sum = 0;
				cnt = 0;
			}
		}
		return max;
	}

	public static void main(String[] args) {
		LongestValidParentheses a = new LongestValidParentheses();
		System.out.println(a.longestValidParentheses("((()()(())"));
	}

}
